// https://www.lintcode.com/problem/ugly-number-ii/my-submissions?_from=ladder&&fromId=6

class Solution {
public:
    /**
     * @param n: An integer
     * @return: return a  integer as description.
     */
     
    // TLE
    // bool isUgly(int num) {
    //     if (num == 0) return false; // 重要  1算true
    //     while (num % 2 == 0) num /= 2;
    //     while (num % 3 == 0) num /= 3;
    //     while (num % 5 == 0) num /= 5;
    //     return num == 1;
    // }
    // int nthUglyNumber(int n) {
    //     if (n == 1) return 1;
    //     int i = 2;
    //     n--;
    //     while(n)
    //     {
    //         if (isUgly(i++)) n--;
    //     }
    //     return --i;
    // }
    
    // O(n)的解法
    // 由于我们已经知道这个公式 uglyNumber = 2^m3^n5^j, 所以，下一个丑数 uglyNumber = Min(lastNumber2, lastNumber3, lastNumber*5)
    // 3个因子2，3，5 的坐标分享同一个数组
    // p2, p3, p5表示待乘2/3/5的数
    // int nthUglyNumber(int n) {
    //     int res[n];
    //     res[0] = 1;
    //     int p2 = 0;
    //     int p3 = 0;
    //     int p5 = 0;
    //     for (int i = 1; i < n; ++i)
    //     {
    //         res[i] = min(res[p2] * 2, min(res[p3] * 3, res[p5] * 5));
    //         if (res[i] == res[p2] * 2) {
    //             p2++;
    //         }
    //         if (res[i] == res[p3] * 3) {
    //             p3++;
    //         }
    //         if (res[i] == res[p5] * 5) {
    //             p5++;
    //         }
    //     }
    //     return res[n - 1];
    // }

    // priority_queue    
        // int nthUglyNumber(int n) {
        //     priority_queue<long,vector<long>,greater<long>>qu;
        //     qu.push(1);
        //     if(n == 1) return 1;
        //     for(int i = 0; i < n - 1; i++){
        //         long tmp = qu.top();
        //         qu.push(tmp*2);
        //         qu.push(tmp*3);
        //         qu.push(tmp*5);
        //         while(qu.top() == tmp)
        //             qu.pop();   //去除重复元素
        //     }
        // return qu.top();
        // }
        
    // set
         int nthUglyNumber(int n) {
            set<long> s; //注意用long
            s.insert(1);
            if(n == 1) return 1;
            for(int i = 0; i < n - 1; i++){
                long tmp = *s.begin();
                s.insert(tmp*2);
                s.insert(tmp*3);
                s.insert(tmp*5);
                while(*s.begin() == tmp)
                    s.erase(s.begin());   //去除重复元素
            }
        return *s.begin();
        }

};